/*
 * Created on 2004/10/24
 *
 * To change the template for this generated file go to
 * Window&gt;Preferences&gt;Java&gt;Code Generation&gt;Code and Comments
 */
package libnetdb.dm.assoc.util;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

/**
 * @author Cheng-Ru Lin
 *
 *
 */
public class MaxHeap implements Heap {
	
	private int size = 0;
	private Object data[] = null;
	private Comparator comp = null;	

	public MaxHeap( int capacity, Comparator comp ) {
		data = new Object[ capacity + 1 ];
		this.comp = comp;
	}
	
	public MaxHeap( int capacity ) {
		this( capacity, new DefaultComparator() );
	}
	
	private void expension() {
		int compacity = data.length * 2;
		Object newData[] = new Object[ compacity ];
		System.arraycopy( data, 0, newData, 0, data.length );
		data = newData;
	}
		
	private boolean more( int i, int j ) {
		return comp.compare( data[i], data[j] ) > 0 ;
	}
	
	private boolean more( Object x, Object y ) {
		return comp.compare( x, y ) > 0 ;		
	}
	
	private void swap( int i, int j ) {
		Object temp = data[ i ];
		data[i] = data[j]; 
		data[j] = temp;
	}
	
	private void heapify( int i ) {
		int t = i, l = i + i, r = l + 1;
		if ( l <= size && more( l, i ) ) t = l;
		if ( r <= size && more( r, t ) ) t = r;
		if ( t != i ) {
			swap( i, t );
			heapify( t );
		}		
	}
	
	public int size() {
		return size;
	}
	
	public Object extract() {
		if ( size == 0 ) return null;
		Object ret = data[1];
		data[1] = data[size];
		data[size--] = null;
		heapify( 1 );
		return ret;
	}
	
	public Object peek() {
		return size > 0 ? data[1] : null;
	}
	
	public void insert( Object object ) {
		if ( size + 1 == data.length ) expension();
		int i = 0, p = 0;
		for( i = ++size; i > 1; i = p ) {
			if( ! more( object, data[ p=(i>>1) ] ) ) break;
			data[i] = data[p];
		}
		data[i] = object; 
	}
	
	public void clear() {
		while( size > 0 )
			data[ -- size ] = null;
	}
	
	public void updateTop( Object object ) {		
		if ( more( data[1], object ) ) {
			data[1] = object;
			heapify( 1 );
		}
	}
	
	static final class DefaultComparator implements Comparator {
		public final int compare(Object o1, Object o2) {
			return ((Comparable) o1 ).compareTo( o2 );
		}		
	}
	
	static public void main( String argv[] ) {
		int data[] = new int[1024];
		MaxHeap heap = new MaxHeap(32);
		Random random = new Random( 0L );
		for( int i = 0; i < data.length; ++i ) {
			data[i] = random.nextInt( 100 );
			heap.insert( new Integer(data[i]) );
		}
		Arrays.sort( data );		
		for( int i=data.length - 1; i >= 0; --i ) {
			Integer x = (Integer) heap.extract();
			if ( x.intValue() != data[i] ) 
				throw new RuntimeException( "Assertion Fail" );
		}
		System.out.println( "Test Successfully" );
	}
}
